package com.lyj.sc.dynamicProgramming.test20220716;

/**
 * @program: code-random
 * @description:
 * @author: lyj
 * @create: 2022-07-11 12:05
 * @version: 1.0
 * @Modifier By:
 **/
public class testweightbagproblem2 {
    public static void testWeightBagProblem(int[] weight,int[] value,int bagsize){
        int len = weight.length;
        //1.定义dp数组
        int [] dp = new int[bagsize+1];
        //2.初始化
        //已经初始为0了
        //3.遍历 只能先遍历物品在背包 而且 背包由大到小 这样才不会把一个物品加两次
        for(int i=0;i<len;i++){
            for(int j=bagsize;j>=weight[i];j--){
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        for (int i = 0; i <=bagsize; i++) {
            System.out.println(dp[i]);
        }
    }
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }
}
